package com.lllkey.dp01bag;


/**
 * k是当前要放第几个包，本程序从后往前开始, m是剩余空间 f(k,m) = f(k-1 ,m ) if(weight[k]>m) k!=0 f(k,m)
 * = max{f(k-1,m),f(k-1,m-weight[k])+vaule[k]} if(weight[k]<=m) k!=0 f(k,m) =
 * value[k] if(weight[k]<=m) k==0 0 if(weight[k]>m) k==0
 * k和m的范围决定了缓冲区cache[][]数组的范围与设置
 * 
 * @author
 * 
 */
public class DP01Bag {

	private static int i;

	/**
	 * 
	 * @param weight
	 * @param value
	 * @param current
	 * @param BagSpace
	 * @param cache
	 *            weight.len*BagSpace的二维数组
	 * @return
	 */
	public static double DP_Bag(int[] weight, int[] value, int current,
			int BagSpace, Double[][] cache) {
		i++;
		if (current == 0) {
			double result;

			if (weight[current] <= BagSpace) {
				result = value[current];

			} else {
				result = 0;

			}

			cache[current][BagSpace] = result;
			return result;
		} else {
			double result;

			if (weight[current] > BagSpace) {

				if (cache[current - 1][BagSpace] != null) {
					result = cache[current - 1][BagSpace];
				} else {
					result = DP_Bag(weight, value, current - 1, BagSpace, cache);
				}

				cache[current][BagSpace] = result;
				return result;

			} else {

				double result1;
				if (cache[current - 1][BagSpace] != null)
					result1 = cache[current - 1][BagSpace];
				else
					result1 = DP_Bag(weight, value, current - 1, BagSpace,
							cache);

				double result2;
				if (cache[current - 1][BagSpace - weight[current]] != null)
					result2 = cache[current - 1][BagSpace - weight[current]]
							+ value[current];
				else
					result2 = DP_Bag(weight, value, current - 1, BagSpace
							- weight[current], cache)
							+ value[current];

				result = result1 > result2 ? result1 : result2;
				cache[current][BagSpace] = result;
				return result;

			}
		}
	}

	public static BagInfo DP_BagDetail(int[] weight, int[] value, int current,
			int BagSpace, Double[][] cache, String[][] bagStrCache) {
		i++;
		if (current == 0) {
			double result;
			String bagStr;

			if (weight[current] <= BagSpace) {
				result = value[current];
				bagStr = value[current] + " ";
			} else {
				result = 0;
				bagStr = "";
			}

			cache[current][BagSpace] = result;
			bagStrCache[current][BagSpace] = bagStr;

			return new BagInfo(result, bagStr);
		} else {
			double result;
			String bagStr;
			if (weight[current] > BagSpace) {

				if (cache[current - 1][BagSpace] != null) {
					result = cache[current - 1][BagSpace];
					bagStr = bagStrCache[current - 1][BagSpace];
				} else {
					BagInfo bagInfo = DP_BagDetail(weight, value, current - 1,
							BagSpace, cache, bagStrCache);
					result = bagInfo.result;
					bagStr = bagInfo.bagStr;
				}

				cache[current][BagSpace] = result;
				bagStrCache[current][BagSpace] = bagStr;
				return new BagInfo(result, bagStr);

			} else {

				double result1;
				String bagStr1;
				if (cache[current - 1][BagSpace] != null) {
					result1 = cache[current - 1][BagSpace];
					bagStr1 = bagStrCache[current - 1][BagSpace];
				} else {
					BagInfo bagInfo = DP_BagDetail(weight, value, current - 1,
							BagSpace, cache, bagStrCache);
					result1 = bagInfo.result;
					bagStr1 = bagInfo.bagStr;
				}

				double result2;
				String bagStr2;
				if (cache[current - 1][BagSpace - weight[current]] != null) {
					result2 = cache[current - 1][BagSpace - weight[current]]
							+ value[current];
					bagStr2 = bagStrCache[current - 1][BagSpace
							- weight[current]]
							+ value[current] + " ";
				} else {
					BagInfo bagInfo = DP_BagDetail(weight, value, current - 1,
							BagSpace - weight[current], cache, bagStrCache);
					result2 = bagInfo.result + value[current];
					bagStr2 = bagInfo.bagStr + value[current] + " ";
				}
				result = result1 > result2 ? result1 : result2;
				bagStr = result1 > result2 ? bagStr1 : bagStr2;
				cache[current][BagSpace] = result;
				bagStrCache[current][BagSpace] = bagStr;
				return new BagInfo(result, bagStr);

			}
		}
	}

	public static BagInfo DP_BagDetailObj(int[] weight, int[] value,
			int current, int BagSpace, BagInfo[][] cache) {
		i++;
		if (current == 0) {
			double result;
			String bagStr;

			if (weight[current] <= BagSpace) {
				result = value[current];
				bagStr = value[current] + " ";
			} else {
				result = 0;
				bagStr = "";
			}
			cache[current][BagSpace] = new BagInfo();
			cache[current][BagSpace].result = result;
			cache[current][BagSpace].bagStr = bagStr;

			return cache[current][BagSpace];
		} else {
			double result;
			String bagStr;
			if (weight[current] > BagSpace) {

				if (cache[current - 1][BagSpace] != null) {
					result = cache[current - 1][BagSpace].result;
					bagStr = cache[current - 1][BagSpace].bagStr;
				} else {
					BagInfo bagInfo = DP_BagDetailObj(weight, value,
							current - 1, BagSpace, cache);
					result = bagInfo.result;
					bagStr = bagInfo.bagStr;
				}

				cache[current][BagSpace] = new BagInfo();
				cache[current][BagSpace].result = result;
				cache[current][BagSpace].bagStr = bagStr;
				return cache[current][BagSpace];

			} else {

				double result1;
				String bagStr1;
				if (cache[current - 1][BagSpace] != null) {
					result1 = cache[current - 1][BagSpace].result;
					bagStr1 = cache[current - 1][BagSpace].bagStr;
				} else {
					BagInfo bagInfo = DP_BagDetailObj(weight, value,
							current - 1, BagSpace, cache);
					result1 = bagInfo.result;
					bagStr1 = bagInfo.bagStr;
				}

				double result2;
				String bagStr2;
				if (cache[current - 1][BagSpace - weight[current]] != null) {
					result2 = cache[current - 1][BagSpace - weight[current]].result
							+ value[current];
					bagStr2 = cache[current - 1][BagSpace - weight[current]].bagStr
							+ value[current] + " ";
				} else {
					BagInfo bagInfo = DP_BagDetailObj(weight, value,
							current - 1, BagSpace - weight[current], cache);
					result2 = bagInfo.result + value[current];
					bagStr2 = bagInfo.bagStr + value[current] + " ";
				}

				if (result1 > result2) {
					result = result1;
					bagStr = bagStr1;
				} else {
					result = result2;
					bagStr = bagStr2;
				}

				cache[current][BagSpace] = new BagInfo();
				cache[current][BagSpace].result = result;
				cache[current][BagSpace].bagStr = bagStr;
				return cache[current][BagSpace];

			}
		}
	}

	public static void main(String[] args) {
		int[] weight = new int[] { 10, 4, 10, 10 };
		int[] value = new int[] { 800, 500, 900, 700 };
		int M = 33;
		Double[][] cache = new Double[weight.length][M + 1];

		// /////method1///////
		System.out.println(DP_Bag(weight, value, weight.length - 1, M, cache));
		System.out.println(i);

		// ////////////////////////////////////////////////////////////////////////////
		System.out.println();
		cache = new Double[weight.length][M + 1];
		i = 0;
		String[][] bagStrCache = new String[weight.length][M + 1];
		// ////////////////////////////////////////////////////////////////////////////

		// /////method2//////////
		BagInfo bagInfo = DP_BagDetail(weight, value, weight.length - 1, M,
				cache, bagStrCache);
		System.out.println(bagInfo.result + ":" + bagInfo.bagStr);
		System.out.println(i);

		// ////////////////////////////////////////////////////////////////////////////
		System.out.println();
		BagInfo[][] bagCache = new BagInfo[weight.length][M + 1];
		i = 0;
		// ////////////////////////////////////////////////////////////////////////////

		// /////method3//////////
		BagInfo bagInfo2 = DP_BagDetailObj(weight, value, weight.length - 1, M,
				bagCache);
		System.out.println(bagInfo2.result + ":" + bagInfo2.bagStr);
		System.out.println(i);

	}
}

class BagInfo {

	public double result;
	public String bagStr;

	public BagInfo() {

	}

	public BagInfo(double result, String bagStr) {
		this.result = result;
		this.bagStr = bagStr;
	}

}
